package com.leetcode.algorithm.y22.m07;

import java.util.ArrayList;
import java.util.List;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 653. 两数之和 IV - 输入 BST
 * 
 * https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/
 * 
 * @author jie.deng
 *
 */
class Question0653Solution01 {
	
	public boolean findTarget(TreeNode root, int k) {
		// 中序遍历+双指针
		List<Integer> list = new ArrayList<>();
		inorderTraversal(root, list);
		int left = 0;
		int right = list.size() - 1;
		while (left < right) {
			int sum = list.get(left) + list.get(right);
			if (sum == k) {
				return true;
			} else if (sum < k) {
				left = left + 1;
			} else {
				right = right - 1;
			}
		}
		return false;
	}
    
	private void inorderTraversal(TreeNode cur, List<Integer> list) {
		if (cur == null) {
			return;
		}
		inorderTraversal(cur.left, list);
		list.add(cur.val);
		inorderTraversal(cur.right, list);
	}
    
}